package de.fuberlin.inf.alp3.ue04;

public class MapImpl<K extends Comparable, V>
        implements Map<K, V>, Clonable<Map<K, V>> {
    private Tuple first = null;
    private Tuple last = null;
    private int len = 0;

    public int getLen() {
        return len;
    }

    private class Tuple {
        private K key;
        private V value;
        private Tuple next;
        private Tuple previous;
        
        public Tuple (K key, V value) {
            this.key = key;
            this.value = value;
        }
        public Tuple next() {
            return this.next;
        }
        public Tuple previous() {
            return this.previous;
        }
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;    // equivalent
        // TODO what about other Map implementations with same content?
        if (!(obj.getClass().equals(this.getClass())))
            return false;
        MapImpl<K,V> theOther = (MapImpl<K,V>) obj;
        if (this.len != theOther.getLen())
            return false;
        // otherwise: compare every single element
        // the following will work for all Map implementations...
        for (Tuple curr = this.first; ; curr = curr.next) {
            try {
                if (!(curr.value.equals(theOther.lookup(curr.key))))
                    return false;
            } catch (NotFound e) {
                return false;
            }
            if (curr == this.last)
                break;
        }
        return true;
    }

    @Override
    public void enter(K key, V val) {
        if (this.empty()) {
            first = last = new Tuple(key, val); // sole element of map
            this.len++;
        }
        else {
            // TODO better: search binary to increase performance!
            Tuple curr = first;
            while ((curr != this.last) && (curr.key.compareTo(key) < 0))
                curr = curr.next;
            if (curr.key.compareTo(key) > 0) {
                // curr.key > key -> insert before
                curr.previous.next = new Tuple(key, val);
                curr.previous.next.next = curr;
                curr.previous.next.previous = curr.previous;
                curr.previous = curr.previous.next;
                this.len++;
            }
            else if (curr.key.compareTo(key) == 0) {
                curr.value = val;
            }
            else {
                // curr.key < key -> insert after as last element
                this.last.next = new Tuple(key, val);
                this.last.next.previous = curr;
                this.last = this.last.next;
                this.len++;
            }
        }
    }

    private boolean empty() {
        return (this.first == null);
    }

    @Override
    public V lookup(K key) throws NotFound {
        Tuple curr = first;
        while ((curr != this.last) && (curr.key.compareTo(key) < 0))
            curr = curr.next;
        if (curr.key.compareTo(key) == 0)
            return curr.value;
        throw new NotFound();
    }

    @Override
    public void merge(Map<? extends K, ? extends V> m) {
        throw new RuntimeException("Not implemented!");
    }

    @Override
    public Map<K, V> copy() {
        MapImpl<K, V> copy = new MapImpl<K, V>();
        copy.first = this.first;
        copy.last = this.last;
        copy.len = this.len;
        return copy;
    }
}